/*
 * @Author: 缄默
 * @Date: 2021-11-16 16:13:32
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-30 16:40:24
 */

//机器人到达指定位置方法数

//经典从递归到动态规划的思路，常看常理解
#include <iostream>
#include <vector>

using namespace std;

int ways1(int N, int M, int K, int P);
int ways2(int N, int M, int K, int P);
int walk1(int N, int M, int K, int P);
int walk2(int N, int M, int K, int P);

int main() {
    cout << ways1(7, 4, 9, 5) << endl;
    cout << ways2(7, 4, 9, 5) << endl;

    return 0;
}

//第一种方法 递归实现
int ways1(int N, int M, int K, int P) {
    if (N < 2 || M > N || K < 1 || P < 1 || P > N) return 0;
    return walk1(N, M, K, P);
}

int walk1(int N, int M, int K, int P) {
    //步数用完时 如果相等证明走到返回1 不然返回0
    if (K == 0) return M == P;
    //最左侧的上一步 只能是从右边到达
    if (M == 1) return walk1(N, M + 1, K - 1, P);
    //最右侧的上一步 只能是从左边到达
    if (M == N) return walk1(N, M - 1, K - 1, P);
    //中间的可从两边到达
    return walk1(N, M + 1, K - 1, P) + walk1(N, M - 1, K - 1, P);
}


//第二种方法 利用动态规划实现
int ways2(int N, int M, int K, int P) {
    if (N < 2 || M > N || K < 1 || P < 1 || P > N) return 0;
    return walk2(N, M, K, P);
}

//观察可以发现对于递归来说 四个变量中有两个变量是不变的，剩下的两个变量所代表的值只与这两个变量有关，
//而与如何到达这个地方无关，因此可以通过这两个变量形成的数组进行记录，形成动态规划

int walk2(int N, int M, int K, int P) {
    vector<int> dp(N + 1, 0);
    dp[P] = 1;
    int last, next;
    for (int i = 1; i <= K; i++) {
        int leftUp = dp[1];
        for (int j = 1; j <= N; j++) {
            int tmp = dp[j];
            if (j == 1) dp[j] = dp[j + 1];
            else if (j == N) dp[j] = leftUp;
            else {
                dp[j] = leftUp + dp[j + 1];
            }
            leftUp = tmp;
        }
    }
    //返回的是初始表的位置
    return dp[M];
}